An important element for providing advanced telecommunications services requiring large bandwidth is a high capacity packet switch capable of interconnecting a plurality of inputs with a plurality of outputs. Typically, such a packet switch is synchronous and the packets routed therein are of fixed length. During a packet switch cycle, a set of packets present at the inputs is synchronously routed through the packet switch to particular ones of the outputs. In some cases, the packet switch is self-routing in which case packets are routed from particular inputs to particular outputs based on an address contained in a header associated with each packet.
An example of a network which can be used to implement a self-routing packet switch is a banyan network. A banyan network can route a set of packets from its inputs to particular outputs based on addresses contained in the packet headers. The banyan network comprises an array of 2.times.2 switching nodes organized in stages. One problem with a banyan network is that it is internally blocking. This means that a switching node may attempt to route two packets to the same node output at the same time, in which case one or both packets will be lost.
However, a banyan network is internally non-blocking if the set of input packets to the banyan network in any packet switch cycle is ordered in ascending or descending order according to destination address. A Batcher network is a network which can order a set of packets present at its inputs in a particular switch cycle in non-decreasing order according to destination address. Like the banyan network, the Batcher network is an array of 2.times.2 switching nodes organized in stages.
Thus, an internally non-blocking packet switch is achieved by connecting a Batcher network and a banyan network together in sequence. The Batcher network sorts incoming packets according to output destination address (i.e. banyan network output address) and the banyan network routes the packets to the desired outputs.
While there are no internal collisions (i.e. there is no internal blocking) in a Batcher-banyan network, there may be external collisions. An external collision occurs if more than one packet is addressed to the same output in a particular switch cycle.
One particular scheme for resolving such output conflicts is disclosed in A. Huang et al, "Starlite: A Wide Band Digital Switch", Proceedings of the 1984 Globcom Conference. This reference discloses a switch known as the Starlite switch In the Starlite switch, packets present at the switch inputs at the start of a switch cycle are routed through a Batcher sorting network. The Batcher sorting network serves to sort the packets in non-decreasing order according to destination (i.e. banyan output) address. At the outputs of the Batcher nerwork, a trap network is used to purge all but one packet addressed to each destination so that after purging only packets with unique destination addresses remain. The packet destination addresses are in strictly increasing or decreasing order, but with holes in the sequence due to purged packets. This packet sequence with holes can cause internal packet collisions in the subsequent banyan network.
Consequently, a concentrator is required in front of the banyan network for skewing all packets towards the topmost or bottommost concentrator outputs to fill in the holes left by the purged packets before the packets are inputted to the banyan network.
In the Starlite switch, in order to deliver the purged packets to their desired outputs, the purged packets are recirculated to some inputs of the Batcher network which are specially dedicated for the re-entry of purged packets. The purged packets re-enter the Batcher network in a subsequent packet switch cycle and are combined with newly arriving packets by the Batcher network to form a single list of packets sorted in non-decreasing order according to destination address.
A concentrator which may be used in the Starlite switch is disclosed in Knauer, U.S. Pat. No. 4,531,209. The concentrator which is disclosed in Knauer can concentrate one list of packets Thus, when the Knauer concentrator is incorporated into the Starlite switch, the packets which are to be inputted to the banyan network emerge from the concentrator in a list without holes and with their order preserved, for example, in increasing order according to destination address.
However, the purged packets are returned to the Batcher sorting network in an unsorted form. This means that the packet switch requires a far more complex Batcher sorting network than would be the case if the purged packets were recirculated back to the switch inputs in concentrated form and with their order preserved. The Batcher sorting network is by far the most complex component of the Starlite switch in terms of number of switching nodes required. If the purged packets were recirculated back to the switch inputs concentrated and with their order preserved, almost half of the hardware required in the Batcher sorting network would be eliminated.
In short, it is a significant shortcoming of the concentrator described in U.S. Pat. No. 4,531,209 that it can concentrate and preserve the order of only one list of packets rather than two lists of packets. (Another prior art concentrator which can concentrate and preserve the order of only one list of packets is described in Cormen et al, "A Hyperconcentrator Switch For Routing Bit Serial Messages", Proceeding of the 1986 Conference on Parallel Processing Session 9a, IEEE Computer Society Press, Washington, D.C. August 1986, pp. 721-728.) A concentrator which concentrates and preserves the order of two lists of packets would provide significant hardware savings in packet switches which utilize recirculating packets such as the Starlite switch. (For another broadband packet switch which utilizes recirculating packets, see also U.S. patent application Ser. No. 240,748, entitled "Broadband Packet Switch With Combined Queuing," filed for J. N. Giacopelli et al on Sept. 2, 1988 and assigned to the assignee hereof now U.S. Pat. No. 4,893,304, Jan. 9, 1990.
In view of the foregoing, it is an object of the present invention to provide a concentrator which can concentrate and preserve the order of two lists of packets, as such a concentrator significantly simplifies the design of broadband packet switches utilizing the recirculation of purged packets.